Search for: All records

Abstract It is natural to generalize the online$$k$$ $k$-Server problem by allowing each request to specify not only a pointp, but also a subsetSof servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a pagep, but also a subsetSof cache slots, and is satisfied by having a copy ofpin some slot inS. We call this problemSlot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family$${\mathcal {S}}\subseteq 2^{[k]}$$ $S\subseteq 2^{\left[k\right]}$of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache sizekand family$${\mathcal {S}}$$ $S$:If all request sets are allowed ($${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ $S=2^{\left[k\right]}\backslash \left\{\varnothing \right\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ($${\mathcal {S}}=\{[k]\}$$ $S=\left\{\right[k\left]\right\}$).As a function of$$|{\mathcal {S}}|$$ $\left|S\right|$andk, the optimal deterministic ratio is polynomial: at most$$O(k^2|{\mathcal {S}}|)$$ $O\left(k^2\right|S\left|\right)$and at least$$\Omega (\sqrt{|{\mathcal {S}}|})$$ $\Omega \left(\sqrt{\left|S\right|}\right)$.For any laminar family$${\mathcal {S}}$$ $S$of heighth, the optimal ratios areO(hk) (deterministic) and$$O(h^2\log k)$$ $O(h^{2}logk)$(randomized).The special case of laminar$${\mathcal {S}}$$ $S$that we callAll-or-One Pagingextends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio forweightedAll-or-One Paging is$$\Theta (k)$$ $\Theta \left(k\right)$. Offline All-or-One Paging is$$\mathbb{N}\mathbb{P}$$ $NP$-hard.Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set$$P$$ $P$ofpages, and is satisfied by fetching any page from$$P$$ $P$into the cache. The optimal ratios for the latter problem (with laminar family of heighth) are at mosthk(deterministic) and$$hH_k$$ $h{H}_k$(randomized). 

On hypergraphs withmhyperedges andnvertices, wherepdenotes the total size of the hyperedges, we provide the following results:We give an algorithm that runs in\(\widetilde{O}(mn^{2k-2})\)time for finding a minimumk-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimumk-cut problem, fork> 2.We give an algorithm that runs in\(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\)time for finding a minimumk-cut in hypergraphs of constant rankr. This algorithm betters the previous best running times for both the minimum cut and minimumk-cut problems for dense hypergraphs.Both of our algorithms are Monte Carlo, i.e., they return a minimumk-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a genericbranching randomized contractiontechnique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs.